package com.example.leetcode.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author haitao
 * @date 2021/11/1 5:46 下午
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class Solution56 {

    public int[][] merge(int[][] intervals) {
        // 数组中无记录
        if (intervals.length == 0) {
            return new int[0][2];
        }
        List<int[]> results = new ArrayList<>();
        // 按照区间第一个数字进行排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < intervals.length; i++) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            // 如果results数组中无元素||results最后一个数组中的R<遍历节点的L
            if (results.size() == 0 || results.get(results.size() - 1)[1] < l) {
                results.add(new int[]{l, r});
            } else {
                // 如果results中的最后一个数组中的R>=遍历的节点L
                results.get(results.size() - 1)[1] = Math.max(results.get(results.size() - 1)[1], r);
            }
        }
        return results.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        Solution56 solution56 = new Solution56();
        System.out.println(Arrays.deepToString(solution56.merge(intervals)));
    }
}
